package com.hspedu.newData.dmsxl.设计题;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-21 
 * @Version: 1.0
 */

// 哈希表+双向链表，自定义双向链表
public class LRUCache {

    // 双向链表
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode pre;
        DLinkedNode next;

        public DLinkedNode() {
        }
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 哈希表
    Map<Integer,DLinkedNode> map = new HashMap<>();
    // 容量
    int size;
    int capacity;
    // 头尾节点
    DLinkedNode head;
    DLinkedNode tail;

    // 构造器
    public LRUCache(int capacity) {
        size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.pre = head;
    }

    // 获取方法
    public int get(int key) {
        // 哈希获取node是否存在
        DLinkedNode node = map.get(key);

        // 不存在，返回-1
        if (node==null){
            return -1;
        }

        // 存在返回val，同时将该节点移动至链表头部实现lru功能
        moveToHead(node);
        return node.value;
    }

    // 添加方法
    public void put(int key, int value) {

        // 哈希获取node是否存在
        DLinkedNode node = map.get(key);

        // 不存在，新建node
        if (node==null){
            DLinkedNode newNode = new DLinkedNode(key,value);
            map.put(key,newNode);
            addToHead(newNode);
            size++;
            // 判断容量是否超出，超出，则删除尾节点
            if (size>capacity){
                DLinkedNode tail = deleteTail();
                map.remove(tail.key);
                size--;
            }
        }else {
            // 存在，直接修改node
            node.value = value;
            moveToHead(node);
        }
    }

    private void moveToHead(DLinkedNode node){
        deleteNode(node);
        addToHead(node);
    }

    private void addToHead(DLinkedNode node){
        node.pre = head;
        node.next = head.next;
        head.next = node;
        node.next.pre = node;
    }

    private DLinkedNode deleteTail(){
        DLinkedNode pre = tail.pre;
        deleteNode(pre);
        return pre;
    }

    private void deleteNode(DLinkedNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}
